class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        cols=len(heights)
        left,right=[0]*cols,[cols]*cols
        stack=[]
        for i in range(cols):
            while stack and heights[i]<=heights[stack[-1]]:
                right[stack[-1]]=i
                stack.pop()
            left[i]=stack[-1] if stack else -1
            stack.append(i)
        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(cols)) if cols>0 else 0
        return ans


'''
执行用时：
60 ms
, 在所有 Python3 提交中击败了
82.32%
的用户
内存消耗：
16.6 MB
, 在所有 Python3 提交中击败了
18.71%
的用户
'''